
// ================================================================================================
// -*- C++ -*-
// File: IndexedPriorityQueue.hpp
// Author: Guilherme R. Lampert
// Created on: 05/10/13
// Brief: Helper priority queue used by the search algorithms.
// ================================================================================================

#ifndef __INDEXEDPRIORITYQUEUE_HPP__
#define __INDEXEDPRIORITYQUEUE_HPP__

#include <vector>

// Priority queue based on an index into a set of keys.
// The priority in this implementation is the lowest valued key
template<class KeyType>
class IndexedPriorityQLow {

public:

	// You must pass the constructor a reference to the std::vector the PQ
	// will be indexing into and the maximum size of the queue.
	inline IndexedPriorityQLow(std::vector<KeyType> & keys, int sizeMax) :
		keyList(keys), heap(), invHeap(), size(0), maxSize(sizeMax)
	{
		heap.assign(maxSize + 1, 0);
		invHeap.assign(maxSize + 1, 0);
	}

	// Test for empty queue.
	inline bool IsEmpty() const
	{
		return (size == 0);
	}

	// To insert an item into the queue it gets added to the end of the heap
	// and then the heap is reordered from the bottom up.
	inline void Insert(int idx)
	{
		assert((size + 1) <= maxSize);

		++size;
		heap[size] = idx;
		invHeap[idx] = size;
		ReorderUpwards(size);
	}

	// To get the min item the first element is exchanged with the lowest
	// in the heap and then the heap is reordered from the top down.
	inline int Pop()
	{
		Swap(1, size);
		ReorderDownwards(1, size - 1);
		return (heap[size--]);
	}

	// If the value of one of the client key's changes then call this with
	// the key's index to adjust the queue accordingly.
	inline void ChangePriority(int idx)
	{
		ReorderUpwards(invHeap[idx]);
	}

private:

	inline void Swap(int a, int b)
	{
		const int temp = heap[a];
		heap[a] = heap[b];
		heap[b] = temp;
		invHeap[heap[a]] = a;
		invHeap[heap[b]] = b;
	}

	inline void ReorderUpwards(int nd)
	{
		// Move up the heap swapping the elements until the heap is ordered
		while ((nd > 1) && (keyList[heap[nd / 2]] > keyList[heap[nd]]))
		{
			Swap(nd / 2, nd);
			nd /= 2;
		}
	}

	inline void ReorderDownwards(int nd, int heapSize)
	{
		// Move down the heap from node 'nd' swapping the
		// elements until the heap is reordered
		while ((2 * nd) <= heapSize)
		{
			int child = (2 * nd);

			// Set child to smaller of nd's two children
			if ((child < heapSize) && (keyList[heap[child]] > keyList[heap[child + 1]]))
			{
				++child;
			}

			// If this nd is larger than its child, swap
			if (keyList[heap[nd]] > keyList[heap[child]])
			{
				Swap(child, nd);

				// move the current node down the tree
				nd = child;
			}
			else
			{
				break;
			}
		}
	}

	std::vector<KeyType> & keyList;
	std::vector<int> heap;
	std::vector<int> invHeap;
	int size, maxSize;
};

#endif // __INDEXEDPRIORITYQUEUE_HPP__
